package demo.practice.leetcode_offer;

public class Offer14_1 {


    public static void main(String[] args) {
        Offer14_1 offer14_1= new Offer14_1();
        offer14_1.cuttingRope(3);
    }

    int[] bucket;

    public int cuttingRope(int n) {
        bucket = new int[n+1];
        return cutting(n);
    }

    private int cutting(int n) {

        if (bucket[n] != 0)
            return bucket[n];

        if (n == 2) {
            return 1;
        }

        int max = 0;
        for (int i = 1; i < n-1; i++) {
            max = Math.max(cutting(n - i) * i, max);
            max= Math.max(max,i*(n-i));
        }

        bucket[n] = max;
        return max;
    }
}
